#!usr/bin/env python  
# -*- coding:utf-8 _*-
""" 
@author:pengfeifu
@file: 快速排序法.py 
@software:PyCharm
@time: 2021/11/21 上午11:13
@email:1324734112@qq.com
@desc： 快速排序法，升序
思路：
    1。取一个元素p（第一个元素），让元素p归位到应该在的位置
    2。列表被元素p分成两部分，左边比p小，右边大
    3。递归完成排序
@function：常用函数
"""


def quick_sort(li, left, right):
    if left < right:
        mid = partition(li, left, right)
        quick_sort(li, left, mid - 1)
        quick_sort(li, mid + 1, right)
        #print(li)


def partition(li, left, right):
    temp = li[left]
    while left < right:
        while left < right and temp < li[right]:  # 从右边找比temp小的数
            right -= 1  # 往前走一步
        li[left] = li[right]  # 不满足条件，或者right移动到了小于temp的位置，进行置换
        while left < right and temp > li[left]:  # 从左边找比temp大的数
            left += 1  # 往前走一步
        li[right] = li[left]
    li[left] = temp   # 把temp值归位
    print(left, li)
    return left


if __name__ == '__main__':
    quick_sort([5, 3, 0, 2, 8, 4, 7, 6], 0, 7)
